package 编辑距离;

public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minDistance("intention","execution"));
//        System.out.println(s.minDistance("horse","ros"));
//        System.out.println(s.minDistance("abcefg","afi"));
//        System.out.println(s.minDistance("afi","abcefg"));
//        System.out.println(s.minDistance("sea","eat"));
    }

    public int minDistance(String word1, String word2) {
        int minLength = 0;
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();

        if(word1.length() <= word2.length()){
            int length = chars1.length;
            //是不是都在 & 是不是从左到右（不一定相粘）出现

            int lastCount = 0;

            while (length > 0){
                int lastIndex = -1;
                int count = 0;
                for (int i = chars1.length - length; i < chars1.length; i++) {
                    char c = chars1[i];
                    int index = word2.indexOf(c,lastIndex+1);
                    if(index>-1){
                        lastIndex = index;
                        count++;
                    }
                }
                if(count == word1.length()){
                    break;
                }
                if(count > lastCount){
                    lastCount = count;
                }
                length--;
            }

            if(lastCount != 0 && chars1[0] != chars2[0]){
                minLength = word2.length() - lastCount + 1;
            }else{
                minLength = word2.length() - lastCount;
            }
        }
        return minLength;
    }
}
